//给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。 
//
// 请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。 
//
// 你可以假设 nums1 和 nums2 不会同时为空。 
//
// 示例 1: 
//
// nums1 = [1, 3]
//nums2 = [2]
//
//则中位数是 2.0
// 
//
// 示例 2: 
//
// nums1 = [1, 2]
//nums2 = [3, 4]
//
//则中位数是 (2 + 3)/2 = 2.5
// 
//

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int target1 = 0, target2 = 0;
        boolean isDouble = true;
        if ((m + n) % 2 != 0) {
            isDouble = false;
        }
        int pos1 = m - 1;
        int pos2 = n - 1;
        int totalNum = (m + n) / 2 + 1;
        if (m == 0) {
            return isDouble ? (nums2[n / 2] + nums2[n / 2 - 1]) / 2.0 : nums2[n / 2];
        } else if (n == 0) {
            return isDouble ? (nums1[m / 2] + nums1[m / 2 - 1]) / 2.0 : nums1[m / 2];
        }
        int[] result = new int[totalNum];
        int i = 0;
        while (i < totalNum) {
            if (pos1 < 0) {
                result[i++] = nums2[pos2--];
                continue;
            }
            if (pos2 < 0) {
                result[i++] = nums1[pos1--];
                continue;
            }
            if (nums1[pos1] > nums2[pos2]) {
                result[i++] = nums1[pos1];
                pos1--;
            } else {
                result[i++] = nums2[pos2];
                pos2--;
            }
        }

        if (isDouble) {
            target1 = result[result.length - 1];
            target2 = result[result.length - 2];
            return (target1 + target2) / 2.0;
        } else {
            target2 = result[result.length - 1];
            return target2;
        }
    }
}